/*-------------------------------------------------------------------------
 *
 * binaryheap.c
 *	  一个简单的二叉堆实现
 *
 * Portions Copyright (c) 2012-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/backend/lib/binaryheap.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <math.h>

#include "lib/binaryheap.h"

static void fc_sift_down(binaryheap *fc_heap, int fc_node_off);
static void fc_sift_up(binaryheap *fc_heap, int fc_node_off);

/*
 * binaryheap_allocate
 *
 * 返回一个指向新分配的堆的指针，该堆具有存储指定数量节点的能力，堆属性由给定的比较函数定义，该函数将被使用 'arg' 指定的附加参数调用。
 */
binaryheap *
binaryheap_allocate(int fc_capacity, binaryheap_comparator fc_compare, void *fc_arg)
{
	int			fc_sz;
	binaryheap *fc_heap;

	fc_sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * fc_capacity;
	fc_heap = (binaryheap *) palloc(fc_sz);
	fc_heap->bh_space = fc_capacity;
	fc_heap->bh_compare = fc_compare;
	fc_heap->bh_arg = fc_arg;

	fc_heap->bh_size = 0;
	fc_heap->bh_has_heap_property = true;

	return fc_heap;
}

/*
 * binaryheap_reset
 *
 * 重置堆为一个空状态，丢失其数据内容，但不丢失分配时传递的参数。
 */
void binaryheap_reset(binaryheap *fc_heap)
{
	fc_heap->bh_size = 0;
	fc_heap->bh_has_heap_property = true;
}

/*
 * binaryheap_free
 *
 * 释放所给 binaryheap 使用的内存。
 */
void binaryheap_free(binaryheap *fc_heap)
{
	pfree(fc_heap);
}

/*
 * 这些实用函数分别返回给定索引处节点的左子节点、右子节点和父节点的偏移。
 *
 * 堆表示为一个节点数组，根节点存储在索引 0。节点 i 的左子节点位于索引 2*i+1，右子节点位于 2*i+2。节点 i 的父节点位于索引 (i-1)/2。
 */

static inline int fc_left_offset(int fc_i)
{
	return 2 * fc_i + 1;
}

static inline int fc_right_offset(int fc_i)
{
	return 2 * fc_i + 2;
}

static inline int fc_parent_offset(int fc_i)
{
	return (fc_i - 1) / 2;
}

/*
 * binaryheap_add_unordered
 *
 * 以 O(1) 将给定数据添加到堆的节点列表末尾，而不保留堆属性。这是为了方便快速地将元素添加到新堆中。要获得有效的堆，必须在之后调用 binaryheap_build()。
 */
void binaryheap_add_unordered(binaryheap *fc_heap, Datum fc_d)
{
	if (fc_heap->bh_size >= fc_heap->bh_space)
		elog(ERROR, "out of binary heap slots");
	fc_heap->bh_has_heap_property = false;
	fc_heap->bh_nodes[fc_heap->bh_size] = fc_d;
	fc_heap->bh_size++;
}

/*
 * binaryheap_build
 *
 * 从通过 binaryheap_add_unordered() 添加的节点中以 O(n) 组装一个有效的堆。除此之外不需要。
 */
void binaryheap_build(binaryheap *fc_heap)
{
	int			fc_i;

	for (fc_i = fc_parent_offset(fc_heap->bh_size - 1); fc_i >= 0; fc_i--)
		fc_sift_down(fc_heap, fc_i);
	fc_heap->bh_has_heap_property = true;
}

/*
 * binaryheap_add
 *
 * 以 O(log n) 的时间将给定的数据添加到堆中，同时保留堆属性。
 */
void binaryheap_add(binaryheap *fc_heap, Datum fc_d)
{
	if (fc_heap->bh_size >= fc_heap->bh_space)
		elog(ERROR, "out of binary heap slots");
	fc_heap->bh_nodes[fc_heap->bh_size] = fc_d;
	fc_heap->bh_size++;
	fc_sift_up(fc_heap, fc_heap->bh_size - 1);
}

/*
 * binaryheap_first
 *
 * 返回指向堆中第一个（根，顶部）节点的指针，而不修改堆。调用者必须确保此例程不在空堆上使用。始终为 O(1)。
 */
Datum binaryheap_first(binaryheap *fc_heap)
{
	Assert(!binaryheap_empty(fc_heap) && fc_heap->bh_has_heap_property);
	return fc_heap->bh_nodes[0];
}

/*
 * binaryheap_remove_first
 *
 * 移除堆中的第一个（根，顶部）节点，并在重新平衡堆后返回指向它的指针。调用者必须确保此例程不在空堆上使用。最坏情况下为 O(log n)。
 */
Datum binaryheap_remove_first(binaryheap *fc_heap)
{
	Datum		fc_result;

	Assert(!binaryheap_empty(fc_heap) && fc_heap->bh_has_heap_property);

	/* 提取根节点，这将是结果 */
	fc_result = fc_heap->bh_nodes[0];

	/* 如果堆包含一个元素，则很简单 */
	if (fc_heap->bh_size == 1)
	{
		fc_heap->bh_size--;
		return fc_result;
	}

	/*
	 * 移除最后一个节点，将其放置在腾出的根位置，并将新的根节点向下筛选到正确的位置。
	 */
	fc_heap->bh_nodes[0] = fc_heap->bh_nodes[--fc_heap->bh_size];
	fc_sift_down(fc_heap, 0);

	return fc_result;
}

/*
 * binaryheap_replace_first
 *
 * 替换非空堆的顶部元素，保留堆属性。在最佳情况下为 O(1)，如果必须回退到将新节点向下筛选，则为 O(log n)。
 */
void binaryheap_replace_first(binaryheap *fc_heap, Datum fc_d)
{
	Assert(!binaryheap_empty(fc_heap) && fc_heap->bh_has_heap_property);

	fc_heap->bh_nodes[0] = fc_d;

	if (fc_heap->bh_size > 1)
		fc_sift_down(fc_heap, 0);
}

/*
 * 将节点筛选到根据比较器它能保持的最高位置。
 */
static void fc_sift_up(binaryheap *fc_heap, int fc_node_off)
{
	Datum		fc_node_val = fc_heap->bh_nodes[fc_node_off];

	/*
	 * 在循环中，node_off'th 数组项是一个“孔”，在概念上保存 node_val，但在结束之前我们实际上不在这里存储 node_val，从而节省了一些不必要的数据复制步骤。
	 */
	while (fc_node_off != 0)
	{
		int			fc_cmp;
		int			fc_parent_off;
		Datum		fc_parent_val;

		/*
		 * 如果这个节点比它的父节点小，则堆条件得以满足，我们完成了。
		 */
		fc_parent_off = fc_parent_offset(fc_node_off);
		fc_parent_val = fc_heap->bh_nodes[fc_parent_off];
		fc_cmp = fc_heap->bh_compare(fc_node_val,
							   fc_parent_val,
							   fc_heap->bh_arg);
		if (fc_cmp <= 0)
			break;

		/*
		 * 否则，交换父节点值与孔，并继续检查节点的新父节点。
		 */
		fc_heap->bh_nodes[fc_node_off] = fc_parent_val;
		fc_node_off = fc_parent_off;
	}
	/* 重新填充孔 */
	fc_heap->bh_nodes[fc_node_off] = fc_node_val;
}

/*
 * 将节点向下筛选，以满足堆的
 * 属性。
 */
static void fc_sift_down(binaryheap *fc_heap, int fc_node_off)
{
	Datum		fc_node_val = fc_heap->bh_nodes[fc_node_off];

	/*
	 * 在循环中，node_off'th 数组项是一个“孔”，在概念上保存 node_val，但在结束之前我们实际上不在这里存储 node_val，从而节省了一些不必要的数据复制步骤。
	 */
	while (true)
	{
		int			fc_left_off = fc_left_offset(fc_node_off);
		int			fc_right_off = fc_right_offset(fc_node_off);
		int			fc_swap_off = 0;

		/* 左子节点是否大于父节点？ */
		if (fc_left_off < fc_heap->bh_size &&
			fc_heap->bh_compare(fc_node_val,
							 fc_heap->bh_nodes[fc_left_off],
							 fc_heap->bh_arg) < 0)
			fc_swap_off = fc_left_off;

		/* 右子节点是否大于父节点？ */
		if (fc_right_off < fc_heap->bh_size &&
			fc_heap->bh_compare(fc_node_val,
							 fc_heap->bh_nodes[fc_right_off],
							 fc_heap->bh_arg) < 0)
		{
			/* 与较大的子节点交换 */
			if (!fc_swap_off ||
				fc_heap->bh_compare(fc_heap->bh_nodes[fc_left_off],
								 fc_heap->bh_nodes[fc_right_off],
								 fc_heap->bh_arg) < 0)
				fc_swap_off = fc_right_off;
		}

		/*
		 * 如果我们没有找到任何可交换的内容，则堆条件
		 * 已满足，我们完成了。
		 */
		if (!fc_swap_off)
			break;

		/*
		 * 否则，将孔与违反堆
		 * 属性的子节点交换；然后继续检查其子节点。
		 */
		fc_heap->bh_nodes[fc_node_off] = fc_heap->bh_nodes[fc_swap_off];
		fc_node_off = fc_swap_off;
	}
	/* 重新填充孔 */
	fc_heap->bh_nodes[fc_node_off] = fc_node_val;
}
